//
// Created by Administrator on 2021/5/29.
//
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        // 二维前缀和
        vector<vector<int>> preSum(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i < preSum.size(); ++i) {
            for (int j = 1; j < preSum[0].size(); ++j) {
                preSum[i][j] = matrix[i - 1][j - 1] + preSum[i][j - 1] + preSum[i - 1][j] - preSum[i - 1][j - 1];
            }
        }
        int ans = 0;
        // 两行之间
        for (int row1 = 0; row1 < m; ++row1) {
            for (int row2 = row1; row2 < m; ++row2) {
                // 两列之间
                for (int col1 = 0; col1 < n; ++col1) {
                    for (int col2 = col1; col2 < n; ++col2) {
                        if (preSum[row2 + 1][col2 + 1] + preSum[row1][col1] -
                            preSum[row2 + 1][col1] - preSum[row1][col2 + 1] == target)
                            ++ans;
                    }
                }
            }
        }
        return ans;
        // 暴力 超时 o(n^4)
    }
};

class Solution2 { // 题解
private:
    int subarraySum(vector<int> &nums, int k) {
        // 利用前缀和 及 hash
        // 求和为k的连续子数组的个数 参见560题
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto &x:nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) {
                count += mp[pre - k];
            }
            mp[pre]++;
        }
        return count;
    }

public:
    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
        int ans = 0;
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) { // 枚举上边界
            vector<int> sum(n);
            for (int j = i; j < m; ++j) { // 枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // 更新每列的元素和
                }
                // 二维变成了一维 在一维数组中有多少和为target的
                ans += subarraySum(sum, target);
            }
        }
        return ans;
    }
};


int main() {
    vector<vector<int>> v{{0, 1, 0},
                          {1, 1, 1},
                          {0, 1, 0}};
    Solution2 sol;
    cout << sol.numSubmatrixSumTarget(v, 0) << endl;
    return 0;
}